package pri.zjy.dynamicProgramming;

/**
 * @author zhangjy
 * @description 打家劫舍 II
 * <p>
 * 这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。
 * @date 2025/5/27 19:18
 */
public class Rob_213 {

    public static void main(String[] args) {
        Rob_213 rob213 = new Rob_213();

//        int[] nums = {2, 3, 2};
        int[] nums = {0, 0};
//        int[] nums = {1, 2, 3, 1};
        System.out.println(rob213.rob(nums ));
    }

    /**
     * dmsxl
     * <p>
     * 分析：
     * 主要是解决 首尾成环 的问题。
     * 如何解决？——既然成环，那么首尾就不同时出现即可。
     * 分为三种情况：
     * 1）考虑偷首元素（考虑并不是一定要偷），不偷尾元素；
     * 2）考虑偷尾元素，不偷首元素；
     * 3）首尾元素都不考虑，考虑偷中间元素。
     * 分别看三种情况，其实就是打家劫舍问题；而情况一、二都包含情况三，因为考虑偷并不是一定要偷。
     * 所以打家劫舍 II的问题拆解为，看三种情况中，哪种能偷到最大的金额。
     */
    public int rob(int[] nums) {
        if (nums.length == 1) return nums[0];

        // 1.考虑偷首元素（考虑并不是一定要偷），不偷尾元素；
        int ans1 = robDP(nums, 0, nums.length - 2);
        // 2.考虑偷尾元素，不偷首元素；
        int ans2 = robDP(nums, 1, nums.length - 1);
        // 3.首尾元素都不考虑，考虑偷中间元素；该情况在前两者中包括。

        return Math.max(ans1, ans2);

    }

    // 打家劫舍[start, end]这个区间的房间
    public int robDP(int[] nums, int start, int end) {
        if ((end - start + 1) == 1) return nums[start];
        if ((end - start + 1) == 2) return Math.max(nums[start], nums[start + 1]);

        // 1.dp[i]表示，考虑偷第 i 号房（可能偷i；也可能不偷，去偷i-1），能偷到的最高金额
        // dp数组大小与nums保持一致, 因为对于不偷首元素来说,其dp[0]=0即可,这样递推公式用到dp[0]不会报错
        int[] dp = new int[nums.length];

        // 2.递推公式
        // dp[i] = Math.max(dp[i-2] + nums[i], dp[i-1]);

        // 3.初始化
        dp[start] = nums[start];
        dp[start + 1] = Math.max(nums[start], nums[start + 1]);

        // 4.遍历
        // 从前往后遍历
        // 这里就是简单的打家劫舍,不用考虑首尾成环的问题,因为真正的环在进入robDP()前就去除了,现在这里是没有环的
        for (int i = 2; i <= end; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
            // 5.打印
            if (dp[i - 1] > dp[i - 2] + nums[i]) {
                // 偷第i-1号房
                System.out.println("dp[" + i + "]=" + dp[i] + " = " + "dp[" + (i - 1) + "]=" + dp[i - 1]);
            } else {
                // 偷第i号房
                System.out.println("dp[" + i + "]=" + dp[i] + " = " + "dp[" + (i - 2) + "]=" + dp[i - 2] + " + " + "nums[" + i + "]=" + nums[i]);
            }
        }

        return dp[end];
    }

    public int rob1(int[] nums) {
        // 1.dp[i]表示，考虑偷第 i 号房（可能偷i，也可能偷i-1），能偷到的最高金额
        // 首尾相连，若偷 i，就不能偷 0 号房
        int[] dp = new int[nums.length];
        // 2.递推公式
        // dp[i] = Math.max(dp[i-2] + nums[i], dp[i-1]);
        // 当要偷第 i 号房时，就不能偷第 0 号。
        // 3.初始化
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        // 4.遍历顺序
        // 从前往后
        for (int i = 2; i < nums.length; i++) {
            // 对于第 i 号房，若要偷，则不能偷第0号。
            // 那怎么知道偷第 i 号房时，前面的有没有偷第 0 号？？？？？？
            if (i == nums.length - 1) {

            }
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return 0;
    }

}
